Replicated State Machine (RSM) is a general method for providing high availability and fault-tolerant services, e.g. software services. In this method, the state machine of the service is replicated and maintained across multiple processes, also referred to as the replica-set, and updated via a sequence of commands which are fed to each of the processes in a globally consistent order. By processing the commands in the same order and in a deterministic fashion, the state of each of the processes in the replica-set can progress in a synchronized and consistent manner.
On occasion, an upgrade of the RSM, such as for introducing an updated version of the RSM implementation or of the service provided thereby, may be required to take place. For example, a bug in the software running the RSM may be fixed, and the bug-free version may need to be deployed among the replica-set processes. Often, a new functionality may be added, in the form of new commands, communication protocols, behavior, or the like, which might not be understood by processes operating under previous versions.